package com.lagou.algorithmus;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 每日算法一题
 */
public class AlgorithmusHash {

    public static void main(String[] args) {
        int[] arr = {3,3};
        int[] ints = twoSum(arr, 6);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 最长连续序列
     * 给定一个未排序的整数数组 nums 找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     */
    public static int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums);
        for (int num : nums) {
            set.add(num);
        }
        int maxLength = 0;
        // 序列长度初始值为1 默认nums至少有一个元素
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            // 判断当前值-1的值是否存在 若不存在则表示此值是序列的起点
            if (!set.contains(nums[i] - 1)) {
                maxLength = 1;
            } else {
                // 当前值-1存在则表示连续
                maxLength++;
            }
            result = Math.max(maxLength, result);
        }
        return result;
    }

    /**
     * 字母异位词
     * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     * 字母异位词 由相同字母组成的词
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        // map 作为字典使用
        Map<String, List<String>> map = new HashMap<>();
        // 遍历排序
        for (int i = 0; i < strs.length; i++) {
            // 对每一个字符串进行排序 若是异位词则排序后的字符串值必定相等 用此值作为key存储
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String newStr = new String(chars);

            if (map.containsKey(newStr)) {
                // 此值存在的话则表示此时遍历的字符串有异位词
                List<String> list = map.get(newStr);
                list.add(strs[i]);
            } else {
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                map.put(newStr, list);
            }

        }
        List<List<String>> result = new ArrayList<>(map.values());
        return result;
    }

    /**
     * 两数之和
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那两个整数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * 你可以按任意顺序返回答案
     */
    public static int[] twoSum(int[] nums, int target) {
        // map作为记录表 用目标值减去数组中遍历的值的结果存储在map中   结果-索引
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int result = target - nums[i];
            if (map.containsKey(result)) {
                // 若包含则表示此时存在两数之和为target
                return new int[]{map.get(result), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }

}
